home *** CD-ROM | disk | FTP | other *** search
/ Aminet 33 / Aminet 33 - October 1999.iso / Aminet / util / misc / VMM_src.lha / VMM / bitmap.c next >
Encoding:
C/C++ Source or Header  |  1995-12-16  |  6.6 KB  |  335 lines
  1. #include <exec/types.h>
  2. #include "defs.h"
  3.  
  4. static char rcsid [] = "$Id: bitmap.c,v 3.5 95/12/16 18:36:59 Martin_Apel Exp $";
  5.  
  6. PRIVATE ULONG *BitMap;
  7. PRIVATE ULONG *BitMapEnd;
  8. PRIVATE ULONG BitMapSize;
  9.  
  10. /* The bitmap looks like this:
  11.  * An allocated bit is symbolized by a set bit.
  12.  * There is one extra long-word after the bitmap used as a sentinel
  13.  * The last but one long-word is filled up with ones and the sentinel
  14.  * is zero. BitMapEnd points to the sentinel.
  15.  */
  16.  
  17. /************************************************************************/
  18.  
  19. int InitMap (ULONG num_slots)
  20.  
  21. {
  22. ULONG num_longwords;
  23. int i;
  24.  
  25. /* Excluding sentinel */
  26. PRINT_DEB ("InitMap (%ld)", num_slots);
  27. num_longwords = (num_slots + 31) / 32;
  28.  
  29. BitMap = DoOrigAllocMem ((num_longwords + 1) * sizeof (ULONG), MEMF_PUBLIC | MEMF_CLEAR);
  30. if (BitMap == NULL)
  31.   return (ERR_NOT_ENOUGH_MEM);
  32.  
  33. BitMapEnd = BitMap + num_longwords;
  34.  
  35. /* Mark last bits as allocated */
  36. if ((num_slots % 32) != 0)
  37.   {
  38.   for (i = num_slots % 32; i < 32; i++)
  39.     *(BitMap + num_longwords - 1) |= (1 << i);
  40.   }
  41.  
  42. BitMapSize = num_slots;
  43. return (SUCCESS);
  44. }
  45.  
  46. /************************************************************************/
  47.  
  48. void KillMap (void)
  49.  
  50. {
  51. ULONG num_longwords;
  52.  
  53. num_longwords = (BitMapSize + 31) / 32;
  54.  
  55. if (BitMap != NULL)
  56.   FreeMem (BitMap, (num_longwords + 1) * sizeof (ULONG));
  57. }
  58.  
  59. /************************************************************************/
  60.  
  61. ULONG AllocSlotNextTo (ULONG neighbour)
  62.  
  63. /* Returns the number of the bit found */
  64. {
  65. ULONG *tmp;
  66. ULONG i;
  67. ULONG mask;
  68.  
  69. #ifdef DEBUG
  70. if (neighbour >= BitMapSize)
  71.   {
  72.   PRINT_DEB ("AllocBitNextTo with invalid neighbour called: %lx", neighbour);
  73.   ColdReboot();
  74.   }
  75. #endif
  76.  
  77. tmp = BitMap + neighbour / 32;
  78.  
  79. while (*tmp == 0xffffffff)
  80.   tmp++;
  81.  
  82. if (tmp == BitMapEnd)
  83.   {
  84.   tmp = BitMap;
  85.   while (*tmp == 0xffffffff)
  86.     tmp++;
  87.   if (tmp == BitMapEnd)
  88.     {
  89. #ifdef DEBUG
  90.     PRINT_DEB ("AllocBitNextTo: Ran out of bits", 0L);
  91.     ColdReboot ();
  92. #endif
  93.     return (0L);
  94.     }
  95.   }
  96.  
  97. /* Find first unset bit in this long-word */
  98. mask = 0x1;
  99. for (i = 0; i < 32; i++)
  100.   {
  101.   if ((*tmp & mask) == 0)
  102.     {
  103.     /* Found it */
  104.     *tmp |= mask;
  105.     return ((tmp - BitMap) * 32 + i);
  106.     }
  107.   mask += mask;
  108.   }
  109. #ifdef DEBUG
  110.   PRINT_DEB ("Internal error: AllocBitNextTo", 0L);
  111.   ColdReboot ();
  112. #endif
  113. return (0L);
  114. }
  115.  
  116. /************************************************************************/
  117.  
  118. #ifdef __GNUC__
  119. PRIVATE __inline__ ULONG NumContiguousSlots (ULONG slot_num, ULONG needed)
  120. #else
  121. PRIVATE ULONG NumContiguousSlots (ULONG slot_num, ULONG needed)
  122. #endif
  123.  
  124. {
  125. /* Determines the number of contiguous slots starting at slot 'num'.
  126.  * Uses doubling a mask instead of shifting each time for efficiency.
  127.  */
  128.  
  129. ULONG *tmp;
  130. ULONG count = 0;
  131. ULONG mask;
  132.  
  133. tmp = BitMap + slot_num / 32;
  134.  
  135. /* PRINT_DEB ("Checking contiguous slots starting at %ld", slot_num); */
  136.  
  137. if ((slot_num % 32) != 0)
  138.   {
  139.   for (mask = (1L << (slot_num % 32)); mask != 0; mask += mask)
  140.     {
  141.     if (*tmp & mask)
  142.       return (count);
  143.     count++;
  144.     }
  145.  
  146.   tmp++;
  147.   }
  148.  
  149. if (count >= needed)
  150.   return (count);
  151.  
  152. while (tmp < BitMapEnd && *tmp == 0L)
  153.   {
  154.   count += 32;
  155.   if (count >= needed)
  156.     return (count);
  157.   tmp++;
  158.   }
  159.  
  160. if (*tmp == 0xffffffff || tmp == BitMapEnd)
  161.   return (count);
  162.  
  163. for (mask = 1; mask != 0; mask += mask)
  164.   {
  165.   if (*tmp & mask)
  166.     return (count);
  167.   count++;
  168.   }
  169.  
  170. /* Should never come here */
  171.  
  172. PRINT_DEB ("NumContiguousSlots: Internal error", 0L);
  173. #ifdef DEBUG
  174. ColdReboot ();
  175. #endif
  176.  
  177. return (0L);        /* To please the compiler */
  178. }
  179.  
  180. /************************************************************************/
  181.  
  182. PRIVATE void AllocateContiguousSlots (ULONG start_slot, ULONG num_slots)
  183.  
  184. {
  185. /* Allocates 'num_slots' starting at 'start_slot'. These slots should
  186.  * have been checked to be free previously.
  187.  */
  188.  
  189. ULONG *tmp;
  190. ULONG mask;
  191.  
  192. /* PRINT_DEB ("Allocating contiguous slots starting at %ld", start_slot); */
  193. /* PRINT_DEB ("Num_slots = %ld", num_slots); */
  194.  
  195. tmp = BitMap + start_slot / 32;
  196.  
  197. if ((start_slot % 32) != 0)
  198.   {
  199.   for (mask = (1L << (start_slot % 32)); mask != 0 && num_slots > 0; mask += mask)
  200.     {
  201. #ifdef DEBUG
  202.     if (*tmp & mask)
  203.       {
  204.       PRINT_DEB ("AllocateContiguousSlots: Trying to allocate already used slot (1)", 0L);
  205.       ColdReboot ();
  206.       }
  207. #endif
  208.  
  209.     *tmp |= mask;
  210.     num_slots--;
  211.     }
  212.  
  213.   tmp++;
  214.   }
  215.  
  216. while (num_slots >= 32)
  217.   {
  218. #ifdef DEBUG
  219.   if (*tmp != 0)
  220.     {
  221.     PRINT_DEB ("AllocateContiguousSlots: Trying to allocate already used slot (2)", 0L);
  222.     ColdReboot ();
  223.     }
  224. #endif
  225.  
  226.   *tmp++ = 0xffffffff;
  227.   num_slots -= 32;
  228.   }
  229.  
  230. for (mask = 1; num_slots > 0; mask += mask)
  231.   {
  232. #ifdef DEBUG
  233.   if (*tmp & mask)
  234.     {
  235.     PRINT_DEB ("AllocateContiguousSlots: Trying to allocate already used slot (3)", 0L);
  236.     ColdReboot ();
  237.     }
  238. #endif
  239.  
  240.   *tmp |= mask;
  241.   num_slots--;
  242.   }
  243. }
  244.  
  245. /************************************************************************/
  246.  
  247. ULONG AllocMultipleSlots (ULONG *num_slots)
  248.  
  249. {
  250. /* Allocates multiple contiguous slots and returns the number of the 
  251.  * first one allocated. If there are not enough contiguous slots 
  252.  * available the largest contiguous chunk is used and its start returned.
  253.  */
  254.  
  255. ULONG *tmp;
  256. ULONG start_of_largest = 0,
  257.       size_of_largest = 0,
  258.       size;
  259. ULONG i;
  260.  
  261. for (tmp = BitMap; tmp < BitMapEnd; tmp++)
  262.   {
  263.   if (*tmp == 0xffffffff)
  264.     continue;
  265.  
  266.   for (i = 0; i < 32; i++)
  267.     {
  268.     if ((*tmp & (1L << i)) == 0)
  269.       {
  270.       size = NumContiguousSlots ((tmp - BitMap) * 32 + i, *num_slots);
  271.       if (size >= *num_slots)
  272.         {
  273.         AllocateContiguousSlots ((tmp - BitMap) * 32 + i, *num_slots);
  274.         return ((tmp - BitMap) * 32 + i);
  275.         }
  276.       else if (size > size_of_largest)
  277.         {
  278.         start_of_largest = (tmp - BitMap) * 32 + i;
  279.         size_of_largest = size;
  280.         break;
  281.         }
  282.       i += size;
  283.       }
  284.     }
  285.   }
  286.  
  287. /* If we have arrived here it means there is no chunk which is large
  288.  * enough available. Use the largest we have found so far.
  289.  */
  290.  
  291. #ifdef DEBUG
  292. if (size_of_largest == 0)
  293.   {
  294.   PRINT_DEB ("AllocMultipleSlots: No slot free", 0L);
  295.   ColdReboot ();
  296.   }
  297. #endif
  298.  
  299. PRINT_DEB ("AllocMultipleSlots: Only %ld contiguous slots available", 
  300.            size_of_largest);
  301. AllocateContiguousSlots (start_of_largest, size_of_largest);
  302. *num_slots = size_of_largest;
  303. return (start_of_largest);
  304. }
  305.  
  306. /************************************************************************/
  307.  
  308. void FreeSlot (ULONG num)
  309.  
  310. {
  311. ULONG *tmp;
  312.  
  313. /* PRINT_DEB ("Freeing slot %ld", num); */
  314.  
  315. #ifdef DEBUG
  316. if (num >= BitMapSize)
  317.   {
  318.   PRINT_DEB ("FreeBit with invalid num called: %lx", num);
  319.   ColdReboot();
  320.   }
  321. #endif
  322.  
  323. tmp = BitMap + num / 32;
  324.  
  325. #ifdef DEBUG
  326. if (!(*tmp & (1 << (num % 32))))
  327.   {
  328.   PRINT_DEB ("Internal error: Free bit which is already free. Slot %ld", num);
  329.   ColdReboot ();
  330.   }
  331. #endif
  332.  
  333. *tmp &= ~(1 << (num % 32));
  334. }
  335.